While Kohen Gadol is a citizen, he belongs to a different "authority" that a King is obligated to respect (see Rambam Melachim 2, 5):
"אבל כהן גדול אינו בא לפני המלך אלא אם רצה ואינו עומד לפניו
אלא המלך עומד לפני כהן גדול שנאמר ולפני אלעזר הכהן יעמוד"
While we read that factually Saul killed the city of Nov (thnks Joel) but can a King Halachicly execute Kohen Gadol that he thinks is מורד במלכות?