Coloring problems on bipartite graphs of small diameter
From MaRDI portal
Publication:831342
DOI10.37236/9931zbMath1464.05143arXiv2004.11173OpenAlexW3164033505MaRDI QIDQ831342
Publication date: 11 May 2021
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.11173
Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- The complexity of surjective homomorphism problems-a survey
- Finding vertex-surjective graph homomorphisms
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Fall colouring of bipartite graphs and Cartesian products of graphs
- Covering graphs with few complete bipartite subgraphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Dominating cliques in \(P_ 5\)-free graphs
- Colorings and orientations of graphs
- Generalized coloring for tree-like graphs
- A Hajós-like theorem for list coloring
- List homomorphisms and circular arc graphs
- List coloring in the absence of a linear forest
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- Open Problems on Graph Coloring for Special Graph Classes
- The NP-Completeness of Edge-Coloring
- Compaction, Retraction, and Constraint Satisfaction
- Precoloring Extension III: Classes of Perfect Graphs
- Reducibility among Combinatorial Problems
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- Surjective H-colouring: New hardness results
- Parameterized Algorithms
This page was built for publication: Coloring problems on bipartite graphs of small diameter
