Discrete Applied Mathematics, ISSN 0166-218X, 03/2019, Volume 257, pp. 361 - 367

A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph...

Edge contraction | Vertex deletion | Chromatic number | MATHEMATICS, APPLIED | Deletion | Graphs | Graph theory | Apexes | Complexity | Mathematics | Combinatorics | Data Structures and Algorithms | Computer Science | Discrete Mathematics

Edge contraction | Vertex deletion | Chromatic number | MATHEMATICS, APPLIED | Deletion | Graphs | Graph theory | Apexes | Complexity | Mathematics | Combinatorics | Data Structures and Algorithms | Computer Science | Discrete Mathematics

Journal Article

Acta Informatica, ISSN 0001-5903, 11/2019, Volume 56, Issue 7, pp. 619 - 648

We introduce in a general setting a dynamic programming method for solving reconfiguration problems. Our method is based on contracted solution graphs, which...

Computer Systems Organization and Communication Networks | Computer Science | Software Engineering/Programming and Operating Systems | Theory of Computation | Information Systems and Communication Service | Logics and Meanings of Programs | Data Structures and Information Theory | Algorithms | Coloring | Graphs | Polynomials | Dynamic programming | Reconfiguration

Computer Systems Organization and Communication Networks | Computer Science | Software Engineering/Programming and Operating Systems | Theory of Computation | Information Systems and Communication Service | Logics and Meanings of Programs | Data Structures and Information Theory | Algorithms | Coloring | Graphs | Polynomials | Dynamic programming | Reconfiguration

Journal Article

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, 2016, Volume 9224, pp. 16 - 300

Conference Proceeding

Journal of Computer and System Sciences, ISSN 0022-0000, 12/2019, Volume 106, pp. 60 - 79

The complexity of Colouring is fully understood for H-free graphs, but there are still major complexity gaps if two induced subgraphs H1 and H2 are forbidden....

Atoms | Graph colouring | Forbidden induced subgraphs | Clique-width | NP-COMPLETENESS | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | SET | COMPLEXITY | COMPUTER SCIENCE, THEORY & METHODS | Computer science | Hardness

Atoms | Graph colouring | Forbidden induced subgraphs | Clique-width | NP-COMPLETENESS | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | SET | COMPLEXITY | COMPUTER SCIENCE, THEORY & METHODS | Computer science | Hardness

Journal Article

2019, ISBN 3030229955, 336

eBook

Algorithmica, ISSN 0178-4617, 01/2020, Volume 82, Issue 1, pp. 20 - 40

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 02/2016, Volume 200, pp. 43 - 51

Let G be a bipartite graph, and let H be a bipartite graph with a fixed bipartition (BH,WH). We consider three different, natural ways of forbidding H as an...

Graph class | Bipartite graph | Clique-width | LINEAR-TIME | MATHEMATICS, APPLIED | SET | CO-GEM-FREE | (P-5,GEM)-FREE GRAPHS | FORBIDDEN SUBGRAPHS

Graph class | Bipartite graph | Clique-width | LINEAR-TIME | MATHEMATICS, APPLIED | SET | CO-GEM-FREE | (P-5,GEM)-FREE GRAPHS | FORBIDDEN SUBGRAPHS

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 09/2017, Volume 86, Issue 1, pp. 42 - 77

A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with...

forbidden induced subgraph | chordal graph | hereditary graph class | clique‐width | clique-width | MATHEMATICS | CO-GEM-FREE | WEIGHT STABLE SET | PARTITIONING PROBLEMS | ALGORITHMS | SPLIT | TRIANGLE-FREE GRAPHS

forbidden induced subgraph | chordal graph | hereditary graph class | clique‐width | clique-width | MATHEMATICS | CO-GEM-FREE | WEIGHT STABLE SET | PARTITIONING PROBLEMS | ALGORITHMS | SPLIT | TRIANGLE-FREE GRAPHS

Journal Article

Theory of Computing Systems, ISSN 1432-4350, 8/2018, Volume 62, Issue 6, pp. 1409 - 1426

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H...

Theory of Computation | Clique number | Square root | Computer Science | Cactus | Treewidth | MATHEMATICS | SQUARE ROOTS | COMPUTER SCIENCE, THEORY & METHODS | SPLIT GRAPHS | Computer science | Computational mathematics | Graph theory | Polynomials | Algorithms

Theory of Computation | Clique number | Square root | Computer Science | Cactus | Treewidth | MATHEMATICS | SQUARE ROOTS | COMPUTER SCIENCE, THEORY & METHODS | SPLIT GRAPHS | Computer science | Computational mathematics | Graph theory | Polynomials | Algorithms

Journal Article

Journal of Computer and System Sciences, ISSN 0022-0000, 09/2019, Volume 104, pp. 202 - 215

We continue the study into the clique-width of graph classes defined by two forbidden induced graphs. We present three new classes of bounded clique-width and...

Graph class | Forbidden induced subgraphs | Clique-width | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | SET | CO-GEM-FREE | COMPUTER SCIENCE, THEORY & METHODS | TRIANGLE-FREE GRAPHS | BIPARTITE GRAPHS

Graph class | Forbidden induced subgraphs | Clique-width | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | SET | CO-GEM-FREE | COMPUTER SCIENCE, THEORY & METHODS | TRIANGLE-FREE GRAPHS | BIPARTITE GRAPHS

Journal Article

Theoretical Computer Science, ISSN 0304-3975, 08/2017, Volume 689, pp. 36 - 47

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are at distance 2 from each...

Square root | k-apex graphs | Linear kernel | COMPUTER SCIENCE, THEORY & METHODS | SPLIT

Square root | k-apex graphs | Linear kernel | COMPUTER SCIENCE, THEORY & METHODS | SPLIT

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 04/2017, Volume 84, Issue 4, pp. 331 - 363

For a positive integer k, a k‐coloring of a graph G=(V,E) is a mapping c:V→{1,2,...,k} such that c(u)≠c(v) whenever uv∈E. The Coloring problem is to decide,...

precoloring extension | graph coloring | forbidden induced subgraph | list coloring | choosability | CHROMATIC NUMBER | CLAW-FREE GRAPHS | TRIANGLE-FREE GRAPHS | NP-COMPLETENESS | MATHEMATICS | UPPER-BOUNDS | 3-COLORABILITY | K-COLORABILITY | ABSENCE | VERTICES | INDEX

precoloring extension | graph coloring | forbidden induced subgraph | list coloring | choosability | CHROMATIC NUMBER | CLAW-FREE GRAPHS | TRIANGLE-FREE GRAPHS | NP-COMPLETENESS | MATHEMATICS | UPPER-BOUNDS | 3-COLORABILITY | K-COLORABILITY | ABSENCE | VERTICES | INDEX

Journal Article

Electronic Notes in Discrete Mathematics, ISSN 1571-0653, 08/2017, Volume 61, pp. 309 - 315

Testing if a given graph G contains the k-vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. The situation changes for...

edge contraction | bipartite graph | path

edge contraction | bipartite graph | path

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 03/2019, Volume 257, pp. 361 - 367

Journal Article

Journal of Computer and System Sciences, ISSN 0022-0000, 11/2017, Volume 89, pp. 410 - 431

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we...

Forbidden induced subgraph | Graph colouring | Diamond-free | Clique-width | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | CO-GEM-FREE | TRIANGLE-FREE GRAPHS | LINEAR-TIME | BOUNDED CLIQUE-WIDTH | COMPUTER SCIENCE, THEORY & METHODS | HEREDITARY CLASSES | FORBIDDEN SUBGRAPHS | BIPARTITE GRAPHS | Logic | Mathematics

Forbidden induced subgraph | Graph colouring | Diamond-free | Clique-width | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | CO-GEM-FREE | TRIANGLE-FREE GRAPHS | LINEAR-TIME | BOUNDED CLIQUE-WIDTH | COMPUTER SCIENCE, THEORY & METHODS | HEREDITARY CLASSES | FORBIDDEN SUBGRAPHS | BIPARTITE GRAPHS | Logic | Mathematics

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 12/2016, Volume 83, Issue 4, pp. 340 - 358

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ‐coloring unless G is a complete...

reconfigurations | Brooks’ Theorem | graph coloring | LIST EDGE-COLORINGS | GRAPH | MATHEMATICS | Brooks' Theorem | COMPLEXITY

reconfigurations | Brooks’ Theorem | graph coloring | LIST EDGE-COLORINGS | GRAPH | MATHEMATICS | Brooks' Theorem | COMPLEXITY

Journal Article

Games and Economic Behavior, ISSN 0899-8256, 03/2018, Volume 108, pp. 245 - 268

We consider multiple partners matching games (G,b,w), where G is a graph with an integer vertex capacity function b and an edge weighting w. If G is bipartite,...

Stable solutions | Cooperative game | Core | Economics and Econometrics | Finance | GAMES | COMPLEXITY | ASSIGNMENT | ECONOMICS

Stable solutions | Cooperative game | Core | Economics and Econometrics | Finance | GAMES | COMPLEXITY | ASSIGNMENT | ECONOMICS

Journal Article

Journal of Combinatorial Optimization, ISSN 1382-6905, 1/2014, Volume 27, Issue 1, pp. 132 - 143

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G...

Reconfigurations | Convex and Discrete Geometry | Operations Research/Decision Theory | Graph diameter | Graph colouring | Mathematics | Theory of Computation | Mathematical Modeling and Industrial Mathematics | Combinatorics | Optimization | Chordal graphs | MATHEMATICS, APPLIED | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS | Computer Science | Discrete Mathematics

Reconfigurations | Convex and Discrete Geometry | Operations Research/Decision Theory | Graph diameter | Graph colouring | Mathematics | Theory of Computation | Mathematical Modeling and Industrial Mathematics | Combinatorics | Optimization | Chordal graphs | MATHEMATICS, APPLIED | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS | Computer Science | Discrete Mathematics

Journal Article

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, 2015, Volume 9079, pp. 167 - 181

Conference Proceeding

20.
Full Text
Updating the complexity status of coloring graphs without a fixed induced linear forest

Theoretical Computer Science, ISSN 0304-3975, 2012, Volume 414, Issue 1, pp. 9 - 19

A graph is H -free if it does not contain an induced subgraph isomorphic to the graph H . The graph P k denotes a path on k vertices. The ℓ - Coloring problem...

Linear forest | Forbidden induced subgraph | Graph coloring | METIS-293161 | MSC-05C | EWI-21077 | IR-82685 | COMPUTER SCIENCE, THEORY & METHODS | 3-COLORABILITY | ALGORITHM | Coloring | Forests | Reproduction | Classification | Graphs | Unions | Complexity

Linear forest | Forbidden induced subgraph | Graph coloring | METIS-293161 | MSC-05C | EWI-21077 | IR-82685 | COMPUTER SCIENCE, THEORY & METHODS | 3-COLORABILITY | ALGORITHM | Coloring | Forests | Reproduction | Classification | Graphs | Unions | Complexity

Journal Article

No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.