On list \(k\)-coloring convex bipartite graphs

DOI10.1007/978-3-030-63072-0_2zbMath1479.05100arXiv2002.02729OpenAlexW3144592529MaRDI QIDQ2056881

Öznur Yaşar Diner, Oriol Serra, Josep Diaz, Maria J. Serna

Publication date: 8 December 2021

Full work available at URL: https://arxiv.org/abs/2002.02729

zbMATH Keywords

list coloringconvex bipartitebiconvex bipartite graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Stochastic network models in operations research (90B15) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Solving problems on generalized convex graphs via mim-width ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ List homomorphism: beyond the known boundaries ⋮ Solving problems on generalized convex graphs via mim-width ⋮ On list \(k\)-coloring convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Bipartite permutation graphs
• Some results concerning the complexity of restricted colorings of graphs
• Precoloring extension. I: Interval graphs
• Algorithmic complexity of list colorings
• On the size of hereditary classes of graphs
• Generalized coloring for tree-like graphs
• Efficient graph representations
• Biconvex graphs: Ordering and algorithms
• Counting \(H-\)colorings of partial \(k-\)trees
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Chordal bipartite graphs of bounded tree- and clique-width
• Three complexity results on coloring \(P_k\)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On list \(k\)-coloring convex bipartite graphs
• Hard coloring problems in low degree planar bipartite graphs
• List coloring in the absence of two subgraphs
• Open Problems on Graph Coloring for Special Graph Classes
• Graph Theory
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Finding Maximum Edge Bicliques in Convex Bipartite Graphs
• The Complexity of the Partial Order Dimension Problem
• Three Partition Refinement Algorithms
• Perfect Elimination and Chordal Bipartite Graphs
• Graph colorings with local constraints -- a survey
• Graph Classes: A Survey
• Treewidth of Chordal Bipartite Graphs
• Precoloring Extension III: Classes of Perfect Graphs
• Reducibility among Combinatorial Problems
• On List Coloring and List Homomorphism of Permutation and Interval Graphs

This page was built for publication: On list \(k\)-coloring convex bipartite graphs