Exercises
Multiple Choice
Articles
Open Problems
Login
9 items
Tagged:
graph coloring
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Graduate
By
Shiva Kintali
on Dec. 5, 2012 | Updated Dec. 6, 2017
Hadwiger’s conjecture and Random graphs
A random graph \(G(n, \frac{1}{2})\) on \(n\) vertices, is obtained by starting with a set of \(n\) and adding every possible edge independently with probability \(\frac{1}{2}\). Hadwiger’s conjectur…
Mathematics
Graph Theory
graph coloring
random graphs
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Dec. 6, 2017
Mycielskian graphs
A factor-critical graph is a graph with \(n\) vertices in which every subset of \(n-1\) vertices has a perfect matching. Let \(\mu(G)\) be the Mycielski graph of an undirected graph \(G\). Prove the …
Mathematics
Graph Theory
graph coloring
0
Undergraduate
By
Shiva Kintali
on Sept. 28, 2013 | Updated Jan. 4, 2018
Chromatic number of interval graphs
An undirected simple graph \(G = (V,E)\) is an interval graph if and only if there exists a family of intervals \({I_u}_{u\in V}\) such that \(I_u\) intersects \(I_v\) if and only if \((u,v)\in E\). …
Mathematics
Graph Theory
clique number
cliques
graph coloring
interval graph
0
Graduate
By
Shiva Kintali
on Nov. 15, 2012 | Updated Dec. 6, 2017
Basics of Perfect Graphs
A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Prove that bipartite graphs are perfect. Prove that the lin…
Mathematics
Graph Theory
basics
bipartite graph
chordal graph
graph coloring
interval graph
perfect graphs
0
Undergraduate
By
Shiva Kintali
on Feb. 12, 2013 | Updated Dec. 6, 2017
Coloring Hamiltonian plane graph
Prove that the faces of a Hamiltonian plane graph can be 4-colored in a such a way that whenever two faces are incident with the same edge they receive different colors.
Mathematics
Graph Theory
graph coloring
planar graphs
0
Undergraduate
By
Shiva Kintali
on July 11, 2012 | Updated Dec. 6, 2017
Edge coloring bipartite graphs
Prove the following : If \(G\) is a regular bipartite graph, then \(G\) has a perfect matching. If \(G\) is \(k\)-regular bipartite graph then it has an edge coloring using exactly \(k\) colors. If…
Mathematics
Graph Theory
edge coloring
graph coloring
0
Undergraduate
By
Shiva Kintali
on Oct. 3, 2013 | Updated Jan. 4, 2018
k-partite subgraph
For each \(k\in \mathbb{N}\) and each simple graph \(G=(V,E)\), prove that \(G\) has a \(k\)-partite subgraph \(H=(V',E')\) (i.e., \(H\) has chromatic number at most \(k\)) such that …
Mathematics
Graph Theory
Probability
graph coloring
probabilistic method
0
Undergraduate
By
Shiva Kintali
on May 9, 2012 | Updated Dec. 6, 2017
$K_4$ subdivision and 3-colorability
Prove that every graph with no subgraph isomorphic to a subdivision of \(K_4\) is 3-colorable.
Mathematics
Graph Theory
graph coloring
0
Undergraduate
By
Shiva Kintali
on June 30, 2012 | Updated Dec. 6, 2017
Coloring graphs with odd cycles
Prove that a graph with at most two odd cycles has chromatic number of at most 3. Let \(G\) be a graph where every two odd cycles have at least a vertex in common. We call such graphs nicely-odd grap…
Mathematics
Graph Theory
graph coloring
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
formal languages
counting
sorting
optimization
bipartite graph
matching
graph labeling
dynamic programming
adjacency matrix
matrices
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×