Publication | Date of Publication | Type |
---|
Maximum cut on interval graphs of interval count four is NP-complete | 2024-04-02 | Paper |
On the degree of trees with game chromatic number 4 | 2024-01-22 | Paper |
On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems | 2023-12-11 | Paper |
MaxCut on permutation graphs is NP‐complete | 2023-10-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q6168453 | 2023-08-08 | Paper |
On the computational difficulty of the terminal connection problem | 2023-05-25 | Paper |
Total colouring | 2022-12-21 | Paper |
On total and edge coloring some Kneser graphs | 2022-08-26 | Paper |
On edge-colouring indifference graphs | 2022-08-16 | Paper |
A general method for forbidden induced subgraph sandwich problem NP-completeness | 2022-04-27 | Paper |
On caterpillars of game chromatic number 4 | 2022-04-27 | Paper |
Even-power of cycles with many vertices are type 1 total colorable | 2022-04-27 | Paper |
On the terminal connection problem | 2022-03-24 | Paper |
Computing the zig-zag number of directed graphs | 2022-03-24 | Paper |
Complexity-separating graph classes for vertex, edge and total colouring | 2020-05-29 | Paper |
On the computational complexity of closest genome problems | 2020-02-14 | Paper |
Timber game as a counting problem | 2019-05-17 | Paper |
On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers | 2019-03-25 | Paper |
On the embedding of cone graphs in the line with distinct distances between neighbors | 2019-02-21 | Paper |
Sandwich and probe problems for excluding paths | 2018-12-03 | Paper |
The sandwich problem for decompositions and almost monotone properties | 2018-10-18 | Paper |
Using SPQR-trees to speed up recognition algorithms based on 2-cutsets | 2018-05-24 | Paper |
The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy | 2017-12-20 | Paper |
Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs | 2017-04-12 | Paper |
Linear-time graph distance and diameter approximation | 2016-10-21 | Paper |
Using SPQR-trees to speed up algorithms based on 2-cutset decompositions | 2016-10-17 | Paper |
The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube | 2016-10-13 | Paper |
https://portal.mardi4nfdi.de/entity/Q2816076 | 2016-07-01 | Paper |
The cost of perfection for matchings in graphs | 2016-06-22 | Paper |
On the equitable total chromatic number of cubic graphs | 2016-06-21 | Paper |
Total-chromatic number and chromatic index of dually chordal graphs | 2016-06-16 | Paper |
The homogeneous set sandwich problem | 2016-06-09 | Paper |
On the total coloring of generalized Petersen graphs | 2016-04-07 | Paper |
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 | 2016-02-18 | Paper |
The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy | 2016-01-05 | Paper |
Linear-Time Approximation Algorithms for Unit Disk Graphs | 2015-11-20 | Paper |
Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs | 2015-09-22 | Paper |
https://portal.mardi4nfdi.de/entity/Q4982370 | 2015-04-09 | Paper |
https://portal.mardi4nfdi.de/entity/Q4982372 | 2015-04-09 | Paper |
https://portal.mardi4nfdi.de/entity/Q4982373 | 2015-04-09 | Paper |
The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem | 2015-02-06 | Paper |
Blind-friendly von Neumann’s Heads or Tails | 2015-02-02 | Paper |
The hunting of a snark with total chromatic number 5 | 2014-05-05 | Paper |
Advancing the Transposition Distance and Diameter through Lonely Permutations | 2014-04-10 | Paper |
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 | 2014-03-31 | Paper |
Edge-colouring and total-colouring chordless graphs | 2014-01-20 | Paper |
Split clique graph complexity | 2014-01-16 | Paper |
The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n-Cube | 2013-12-06 | Paper |
Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs | 2013-09-13 | Paper |
Complexity separating classes for edge-colouring and total-colouring | 2013-08-06 | Paper |
On Coloring Problems of Snark Families | 2013-07-23 | Paper |
Skew partition sandwich problem is NP-complete | 2013-07-19 | Paper |
The P versus NP-complete dichotomy of some challenging problems in graph theory | 2012-11-22 | Paper |
https://portal.mardi4nfdi.de/entity/Q2918472 | 2012-10-06 | Paper |
https://portal.mardi4nfdi.de/entity/Q2918477 | 2012-10-06 | Paper |
Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges | 2012-05-13 | Paper |
Total chromatic number of {square,unichord}-free graphs | 2012-05-13 | Paper |
Split Clique Graph Complexity | 2011-12-16 | Paper |
The chain graph sandwich problem | 2011-11-17 | Paper |
On the forbidden induced subgraph sandwich problem | 2011-10-27 | Paper |
Total chromatic number of unichord-free graphs | 2011-10-27 | Paper |
https://portal.mardi4nfdi.de/entity/Q3011750 | 2011-06-29 | Paper |
A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs | 2011-06-22 | Paper |
Unitary Toric Classes, the Reality and Desire Diagram, and Sorting by Transpositions | 2011-06-17 | Paper |
Complexity dichotomy on partial grid recognition | 2011-05-10 | Paper |
Transitive orientations in bull-reducible Berge graphs | 2011-04-19 | Paper |
The external constraint 4 nonempty part sandwich problem | 2011-04-19 | Paper |
Enclosing weighted points with an almost-unit ball | 2010-09-01 | Paper |
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs | 2010-08-13 | Paper |
The polynomial dichotomy for three nonempty part sandwich problems | 2010-08-13 | Paper |
Decompositions for edge-coloring join graphs and cobipartite graphs | 2010-08-13 | Paper |
\(2K_{2}\) vertex-set partition into nonempty parts | 2010-04-27 | Paper |
Chromatic index of graphs with no cycle with a unique chord | 2010-03-09 | Paper |
The pair completion algorithm for the homogeneous set sandwich problem | 2010-01-18 | Paper |
Hamiltonian paths in odd graphs | 2010-01-12 | Paper |
Note on the homogeneous set sandwich problem | 2009-08-27 | Paper |
Kinetic hanger | 2009-07-09 | Paper |
The complexity of clique graph recognition | 2009-05-28 | Paper |
A NEW QUANTUM ALGORITHM FOR SOLVING THE MINIMUM SEARCHING PROBLEM | 2008-11-03 | Paper |
Clique Graph Recognition Is NP-Complete | 2008-09-04 | Paper |
The polynomial dichotomy for three nonempty part sandwich problems | 2008-06-05 | Paper |
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs | 2008-06-05 | Paper |
Sufficient conditions for a graph to be edge-colorable with maximum degree colors | 2008-06-05 | Paper |
2K2 vertex-set partition into nonempty parts | 2008-06-05 | Paper |
On the generation of bicliques of a graph | 2007-09-19 | Paper |
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs | 2007-09-03 | Paper |
On the generation of bicliques of a graph | 2007-05-29 | Paper |
Bull-Reducible Berge Graphs are Perfect | 2007-05-29 | Paper |
Loop Graphs and Asteroidal Sets | 2007-05-29 | Paper |
https://portal.mardi4nfdi.de/entity/Q3439695 | 2007-05-29 | Paper |
Tree loop graphs | 2007-04-18 | Paper |
https://portal.mardi4nfdi.de/entity/Q3424778 | 2007-03-05 | Paper |
Algorithms for the homogeneous set sandwich problem | 2006-11-06 | Paper |
Extended skew partition problem | 2006-10-30 | Paper |
A characterization of \(P_{4}\)-comparability graphs | 2006-10-30 | Paper |
https://portal.mardi4nfdi.de/entity/Q5492568 | 2006-10-16 | Paper |
The sandwich problem for cutsets: clique cutset, \(k\)-star cutset | 2006-08-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q5708521 | 2005-11-18 | Paper |
https://portal.mardi4nfdi.de/entity/Q5461522 | 2005-07-26 | Paper |
Generating bicliques of a graph in lexicographic order | 2005-06-30 | Paper |
FindingH-partitions efficiently | 2005-06-07 | Paper |
The perfection and recognition of bull-reducible Berge graphs | 2005-06-07 | Paper |
Optimizing Bull-Free Perfect Graphs | 2005-02-28 | Paper |
Stable skew partition problem | 2004-11-23 | Paper |
On decision and optimization (\(k\),\(l\))-graph sandwich problems | 2004-11-23 | Paper |
On the complexity of the approximation of nonplanarity parameters for cubic graphs | 2004-08-06 | Paper |
The stable marriage problem with restricted pairs. | 2004-03-14 | Paper |
Decompositions for the edge colouring of reduced indifference graphs. | 2003-08-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q4414488 | 2003-07-25 | Paper |
On the structure of bull-free perfect graphs. II: The weakly chordal case | 2003-03-27 | Paper |
Kinetic heap-ordered trees: Tight analysis and improved algorithms | 2003-01-22 | Paper |
A note on transitive orientations with maximum sets of sources and sinks | 2002-08-29 | Paper |
The graph sandwich problem for 1-join composition is NP-complete | 2002-08-29 | Paper |
https://portal.mardi4nfdi.de/entity/Q2758333 | 2002-07-28 | Paper |
https://portal.mardi4nfdi.de/entity/Q4508373 | 2002-05-14 | Paper |
https://portal.mardi4nfdi.de/entity/Q4487452 | 2002-03-14 | Paper |
https://portal.mardi4nfdi.de/entity/Q2777504 | 2002-03-07 | Paper |
https://portal.mardi4nfdi.de/entity/Q2741455 | 2001-10-24 | Paper |
https://portal.mardi4nfdi.de/entity/Q2741456 | 2001-10-24 | Paper |
SPLITTING NUMBER is NP-complete | 2001-10-07 | Paper |
https://portal.mardi4nfdi.de/entity/Q2741377 | 2001-09-23 | Paper |
Recognition of quasi-Meyniel graphs | 2001-01-01 | Paper |
A class of \(\beta\)-perfect graphs | 2000-12-28 | Paper |
https://portal.mardi4nfdi.de/entity/Q4521527 | 2000-12-19 | Paper |
https://portal.mardi4nfdi.de/entity/Q4508371 | 2000-10-03 | Paper |
https://portal.mardi4nfdi.de/entity/Q4232795 | 1999-08-23 | Paper |
https://portal.mardi4nfdi.de/entity/Q4252393 | 1999-06-17 | Paper |
Even and odd pairs in comparability and in \(P_4\)-comparability graphs | 1999-05-31 | Paper |
https://portal.mardi4nfdi.de/entity/Q4393307 | 1998-10-05 | Paper |
On edge-colouring indifference graphs | 1998-07-22 | Paper |
https://portal.mardi4nfdi.de/entity/Q4390724 | 1998-05-26 | Paper |
Path parity and perfection | 1998-01-12 | Paper |
Sources and sinks in comparability graphs | 1997-09-29 | Paper |
On the structure of bull-free perfect graphs | 1997-05-11 | Paper |
A linear-time algorithm for proper interval graph recognition | 1997-02-28 | Paper |
https://portal.mardi4nfdi.de/entity/Q4304381 | 1994-10-10 | Paper |