A New Algorithm for On-line Coloring Bipartite Graphs

DOI10.1137/060668675zbMath1181.05035OpenAlexW2132095827MaRDI QIDQ3614195

Daniël Paulusma, Agostino Capponi, Hajo J. Broersma

Publication date: 16 March 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:BROsiamjdm08

zbMATH Keywords

bipartite graphon-line coloring(on-line) chromatic number(on-line) competitive

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ On the complexity of injective colorings and its generalizations ⋮ Symbolic computation of strong Gram congruences for Cox-regular positive edge-bipartite graphs with loops ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ A Coxeter spectral classification of positive edge-bipartite graphs. I: Dynkin types \(\mathcal{B}_n\), \(\mathcal{C}_n\), \(\mathcal{F}_4\), \(\mathcal{G}_2\), \(\mathbb{E}_6\), \(\mathbb{E}_7\), \(\mathbb{E}_8\) ⋮ Open Problems on Graph Coloring for Special Graph Classes

This page was built for publication: A New Algorithm for On-line Coloring Bipartite Graphs