On-Line Coloring of H-Free Bipartite Graphs

DOI10.1007/11758471_28MaRDI QIDQ3434564zbMATH OpenOpenAlexFDO

Authors Agostino Capponi, Daniël Paulusma, Hajo Broersma

Publication date 2 May 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11758471_28

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Recommendations

• A New Algorithm for On-line Coloring Bipartite Graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• An on-line competitive algorithm for coloring P₈-free bipartite graphs
• An on-line competitive algorithm for coloring bipartite graphs without long induced paths
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs

Cited in

(7)

• Bounded families for the on-line \(t\)-relaxed coloring
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs
• An on-line competitive algorithm for coloring P₈-free bipartite graphs
• A New Algorithm for On-line Coloring Bipartite Graphs
• An on-line competitive algorithm for coloring bipartite graphs without long induced paths
• Incorporating predictions in online graph coloring algorithms
• Online hypergraph coloring

This page was built for publication: On-Line Coloring of H-Free Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434564)